| |
| description |
11 pages
|
|
We develop a technique that uses pebbles in a very economical way
for simulating a multi-counter automaton on a sequence of input
strings and maintain a count of those strings accepted by the
counter automaton. Based on this result we show the failure of a
previously proposed method for constructing witness sets separating
classes of languages accepted by pebble automata with an increasing
number of pebbles. We also give a recognition algorithm for another
family of languages suspected to separate the lower levels of the
hierarchy.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-1997-07/TR-1997-07.pdf
|
| contributor |
Theoretische Informatik (IFI)
|
| format |
application/pdf
|
| subject |
Models of Computation (CR F.1.1)
|
| Complexity Classes (CR F.1.3)
|
| Formal Languages (CR F.4.3)
|
| relation |
Technical Report No. 1997/07
|